package cn.edu.leetcode.其他;

public class 最大子序和 {

    public static void main(String[] args) {

        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
    }

    public static int maxSubArray(int[] nums) {

        int i = 0, j = 1, sum = nums[i], max = sum;
        for (; j < nums.length; j++) {
            if (sum < 0) {
                i=j;
                sum = nums[i];
                if (max < sum){
                    max = sum;
                }
            }else {
                sum += nums[j];
                if (max < sum){
                    max = sum;
                }
            }
        }
        return max;
    }
}
